\section{整 数同 余}

\begin{frame}{整 数同 余}
  \pause
Gauss 在其 21 岁著作 Disquisitiones Arithmeticae (《算术研究》, 1801 年出版)中， 开篇就引人同余概念， 影响深远。

\pause
如果时钟的时针正指向 10 点整，那么再过 4 点钟指向几点呢? 答曰 2 点。
\pause
如果今天是星期五， 那么再过3 天是星期几呢? 答曰星期一。 
\pause
按键一次是开电视机， 按键两次呢? 等于没按键。 
\pause
此类现象很多， 引至如下定义。

\pause
\begin{definition}%定义1
设 $m, a, b \in \mathbb{Z}$ (即为整数), $m \neq 0$, 如果
\[
  m \mid(a-b),
\]
则称 $a$ 与 $b$ 对\emph{模 $m$ 同余} ($a$ is congruent to $b$ modulo $m)$, 
\pause
记为 $a \equiv b\,(\bmod~m)$. 
\pause
称 $m$ 为\emph{模} (modulus\footnote{复数的模为 moduli}).
\end{definition}
 \end{frame}

 \begin{frame}

由定义可知，同余关系有如下各种等价的表述：
\pause
\[
  \begin{aligned}
  a \equiv b \quad \left(\mod m\right) & \Leftrightarrow a-b=m k \quad(\text{对某~} k \in \mathbb{Z})\\
  \pause
  & \Leftrightarrow a=b+m k \\
  \pause
& \Leftrightarrow \text { 在忽略不计~} m \text {~的倍数的意义下，~} a \text {~与~} b \text {~相等 } \\
\pause
& \Leftrightarrow a \text { 与$b$ 除以 $m$ 的余数相同。 }
\end{aligned}
\]
\pause
符号``$\equiv$''称为\emph{同余号}，读作 “同余于” , 带同余号的表达式称为\emph{同余式} (congruence). 
\pause
同余式的运算称为 “\emph{模算术}” (modular arithmetic)，是 Gauss 开创的， 影响深远。
\pause
 例如： 
 \[
   14 \equiv 2 \left(\mod 12\right),\quad 
   \pause
   8 \equiv 1 \left(\mod 7\right), \quad 
   \pause
   14 \equiv 0 \left(\mod 7\right),\quad
   \pause
   1+1 \equiv 0 \left(\mod 2\right).
 \]

 \pause
 以后我们通常设 $m \geqslant 2$. 这是因为 $m \mid(a-b)$ 与 $(-m) \mid(a-b)$ 相当， 故模 $-m$与模 $m$ 没有区别。

 \pause
 由带余除法 $a=m q+r$ 知，$a \equiv r \left(\mod m\right)$, 即整数 $a$ 总是同余于其 (剩) 余数 $r$. 
\pause
 因此， 实际在同余式的模运算中， 我们经常以(剩)余数代替原数， 因为余数小， 而且只有有限个， 这就简化了运算， 容易得到简洁优美的结论。
\pause
 (剩) 余数的集合，即 $S=\{0,1,2, \cdots, m-1\}$ ，叫做一个“\emph{剩余系}”.
 \end{frame}

 \begin{frame}

“同余”与 “相等”有许多类似性质， 例如如下定理。

\pause
\begin{theorem}%定理1
同余关系满足如下性质 (对任意 $a, b, c, d, m \in \mathbb{Z}, m \neq 0$):
\begin{enumerate}
 \item (传递性) 若 $a \equiv b \left(\mod m\right), b \equiv c \left(\mod m\right)$, 则 $a \equiv c \left(\mod m\right)$.

  \item （对称性）若 $a \equiv b \left(\mod m\right)$ ，则 $b \equiv a \left(\mod m\right)$.

   \item (自反性)总有 $a \equiv a \left(\mod m\right)$.
\pause
   \item (同余式相加) 若 $a \equiv b \left(\mod m\right), c \equiv d \left(\mod m\right)$, 则 $a+c \equiv b+d \left(\mod m\right)$.

   \item (同余式相乘) 若 $a \equiv b \left(\mod m\right), c \equiv d \left(\mod m\right)$, 则 $a c \equiv b d \left(\mod m\right)$.特别地， 由 $a \equiv b \left(\mod m\right)$ 可知 $a^{k} \equiv b^{k} \left(\mod m\right)$ 对任意正整数 $k$ 成立。

\pause
   \item（同余式约化）若 $a \equiv b \left(\mod m\right)$, 且 $d\mid a, d\mid b$, 则
   \[
 \frac{a}{d} \equiv \frac{b}{d} \quad \left(\mod \frac{m}{(d, m)}\right)
 \]
 特别， (i) 若 $d$ 与 $m$ 互素， 则 $a / d \equiv b / d \left(\mod m\right)$.

 (ii) 若 $d \mid m$ ，则 $a / d \equiv b / d \left(\mod m / d\right)$.
\pause
 \item 设 $m_{i}$ 为非零整数， 则 $a \equiv b\left(\mod m_{i}\right)$ ($i=1, \cdots, s$) 当且仅当
 \[
 a \equiv b \quad\left(\mod \left[m_{1}, \cdots, m_{s}\right]\right) .
 \]
 \end{enumerate}
\end{theorem}

\end{frame}

\begin{frame}
  \begin{proof}
   主要用同余的定义和各种等价条件， 证明都很简单， 举重要的如下。

 (1) 已知条件为： 除以 $m$ 时， $a$ 与 $b$ 的余数相同， $b$ 与 $c$ 的余数相同。 所以 $a$ 与 $c$ 的余数相同， 即知 $a \equiv c \left(\mod m\right)$.

  (5) 已知条件为： $a=b+m k, c=d+m j(k, j \in \mathbb{Z})$. 二式相乘得
\[
  a c=b d+(m k d+m j b+m m k j),
\]
即得 $a c \equiv b d \left(\mod m\right)$.

(6) $m \mid(a-b)$ 相当于 $\frac{m}{(d, m)} \left\lvert\, \frac{a-b}{d} \frac{d}{(d, m)}\right.$, 而 $\frac{m}{(d, m)}$ 与 $\frac{d}{(d, m)}$ 互素， 故
\[
  \left.\frac{m}{(d, m)}~\right\rvert~\frac{a-b}{d}.
\]

 (7)  $a \equiv b\left(\mod m_{i}\right)$ ($i=1, \cdots, s$) 相当于 $m_{i} \mid(a-b)$ ($i=1, \cdots, s$), 即 $a-b$是 $\left\{m_{i}\right\}$ 的公倍数， 必是 $\left\{m_{i}\right\}$ 的最小公倍数的倍数， 即 $\left[m_{1}, \cdots, m_{s}\right] \mid(a-b)$.
 \end{proof}
\pause
总之， 同余式和等式性质几尽相同， 只在除法 (约化)时， 要区分情况。正是：
 \begin{poem}
  “同余”“相等”两相妒， 唯当约化问归处。
\end{poem}

\end{frame}

\begin{frame}

 因 $k \equiv k \left(\mod m\right)$, 故由 (4) 和 (5) 知， 同余式两边可加或乘同一整数。
  例如，由 $22 \equiv 8 \left(\mod 7\right)$, 约去 $2$, 因 $(2,7)=1$, 可得
\[
  11 \equiv 4 \quad \left(\mod 7\right).
\]
由 $15 \equiv 3 \left(\mod 12\right)$, 约去 $3$, 因 $3 \mid 12$, 故得
\[
  5 \equiv 1 \quad \left(\mod 4\right).
\]

\pause
同余式的用途很多， 以下举数例。

\begin{example}%例1
  求 $3^{2049}, 3^{2051}$ 除以 $13$ 的余数。
\end{example}

\pause
\begin{solution*}%解
  因 $3^{3}=27 \equiv 1 \left(\mod 13\right)$, 我们有 
  \[
  \begin{aligned}
      3^{2049}&= 3^{3 k} \equiv 1^{k}=1\left(\mod 13\right), \\
      \pause
      3^{2051}&= 3^{3k+2}=3^{3k}\cdot 3^2\equiv 1^k\cdot 3^2=9\left(\mod 13\right), 
    \end{aligned}
\]
\pause
  故
  $3^{2049}, 3^{2051}$除以$13$的余数分别为$1, 9$.
\end{solution*}
 \end{frame}

\begin{frame}



\begin{example}%例2
考虑如何判断 $9$ 整除 $n$, 即 $n \equiv 0 \left(\mod 9\right)$. 设整数的十进位表示为
\[
n=a_{s} 10^{s}+\cdots+a_{1} 10+a_{0} \quad\left(0 \leqslant a_{i} \leqslant 9\right)
\]
因 $10 \equiv 1 \left(\mod 9\right), 10^{i} \equiv 1 \left(\mod 9\right)$, 故 $9 \mid n$ 相当于
\[
0 \equiv n=a_{s} 10^{s}+\cdots+a_{1} 10+a_{0} \equiv a_{s}+\cdots+a_{1}+a_{0} \quad \left(\mod 9\right)
\]
即 $9\mid n \Leftrightarrow 9\mid  a_{s}+\cdots+a_{1}+a_{0}$ ( $n$ 的各位数字之和 $)$.

\pause
而在求 $n$ 的各位数字之和 $ \left(\mod 9\right)$ 时， 可以不断舍弃 $9$, 故此法名为\emph{弃九法}。 例如 $97263$ 不断弃九之后化为 $7263$, 及 $63$, 及 $0$.

\pause
弃九法可应用于检查运算是否正确：若 $a b=c$, 则应 $a b \equiv c \left(\mod 9\right)$. 故若后者不对， 则前者不对。 例如， 欲检验
\[
467122 \cdot 21691=9382633212
\]
求各数的各位数字之和的余数(可不断弃九， 例如 $4+6$ 化为 $1$, 实为模 $9$), 得
\[
4 \cdot 1 \equiv 3
\]
故原乘式不对。

\pause
同理， $3$ 整除 $n$ 当且仅当 $3$ 整除各位数字之和。
\end{example}
\end{frame}

\begin{frame}
  \begin{example}%例3
    由定理1(7)知：对任意整数 $a, b$,
  \begin{enumerate}
    \item $a \equiv b \left(\mod 6\right)$
    当且仅当 $\begin{cases}
      a \equiv b \left(\mod 2\right) \\
      a \equiv b \left(\mod 3\right).
  \end{cases}$
  \pause
\item $\begin{cases}
      a \equiv b \left(\mod 4\right) \\
    a \equiv b \left(\mod 6\right) \\
    a\equiv b\left(\mod 9\right)
\end{cases}$
当且仅当 
$a \equiv b \left(\mod 36\right)$.
\end{enumerate}
\end{example}
%\pause
%\begin{proof}
% 若 $a \equiv b \left(\mod 6\right)$, 则 $6 \mid(a-b)$, 故 $2 \mid(a-b)$ 且 $3 \mid(a-b)$, 即
% \[
% a \equiv b \quad \left(\mod 2\right) \quad \text { 且 } \quad a \equiv b \quad \left(\mod 3\right) .
% \]
% 反之， 若 $a \equiv b \left(\mod 2\right)$ 且 $a \equiv b \left(\mod 3\right)$, 则 $2 \mid(a-b)$ 且 $3 \mid(a-b)$, 故 $6 \mid(a-b)$ （这是因为：记 $a-b=p_{1} \cdots p_{s}$ 为其素因子分解，由 $2 \mid(a-b)$ 且 $3 \mid(a-b)$ 知可设 $p_{1}=2, p_{2}=3$, 从而 $\left.a-b=p_{1} p_{2} p_{3} \cdots p_{s}=2 \cdot 3 \cdot p_{3} \cdots p_{s}\right)$, 从而 $a \equiv b \left(\mod 6\right)$.
% \end{proof}
%
%\pause
%例3 可推广， 我们后面会专门讨论。 读者不难自证： 若 $m_{1}, m_{2}$ 互素， 则 $a \equiv b \left(\mod m_{1} m_{2}\right)$ 相当于 $a \equiv b \left(\mod m_{1}\right)$ 且 $a \equiv b \left(\mod m_{2}\right)$.
\pause
 \begin{example}%例4
   若 $a \equiv b \left(\mod m\right)$, 则 $a^{k} \equiv b^{k} \left(\mod m\right)$ (对任意正整数 $k$. 由定理 $\left.1(5)\right)$.故对任意整系数多项式 $f(x)=c_{0}+c_{1} x+\cdots+c_{n} x^{n}=\sum_{k=0}^{n} c_{k} x^{k}$, 其中 $c_{0}, \cdots, c_{n}$ 为整数， 均有
   \[
   f(a) \equiv f(b) \quad \left(\mod m\right)
 \]
 这是因为 $c_{k} a^{k} \equiv c_{k} b^{k} \left(\mod m\right)$, 故 $\sum_{k=0}^{n} c_{k} a^{k} \equiv \sum_{k=0}^{n} c_{k} b^{k} \left(\mod m\right)$.
 \end{example}
 \end{frame}

\begin{frame}


\begin{example}%例5
解不定方程 $167 x+23 y=1$.
\end{example}
\pause
\begin{solution*}%解
  化为同余式 $167 x \equiv 1 \left(\mod 23\right)$, 即 $6 x \equiv 1\left(\mod 23\right)$.
  注意到$4\cdot 6\equiv 1\left(\mod 23\right)$, 这相当于
  $x \equiv 4 \left(\mod 23\right)$. 故得
\[
  x=4+23 k.
\]
代人方程得 $y=-29-167 k$ ($k \in \mathbb{Z}$).
\end{solution*}

\pause
  \begin{example}%例6
  固定互素正整数 $m>n$. 将数字 $1,2, \cdots, m-1$ 按如下规则染色 (染成各种颜色):

(i) $k$ 与 $m-k$ 染同色 (对任意 $k$ );

(ii) $k$ 与 $|n-k|$ 染同色 (当 $k \neq n$).

试问共染成几种颜色?
\end{example}
 \end{frame}

\begin{frame}


\begin{solution*}%解
  我们可先将模 $m$ 同余的数皆染为同色 (因 $1,2, \cdots, m-1$ 互不同余)。
那么规则 (i) 化为： $k$ 与 $-k$ 同色。 从而规则 (ii) 中的绝对值符号不再需要 (即 $k$, $n-k, k-n$ 同色).

\pause
因 $m, n$ 互素， 故
\[
u m+v n=1 \quad \text { (Bézout 等式), }
\]
\pause
两边同乘 $a$ (对整数 $a \nequiv 0 \left(\mod m\right)$) 得
\[
a=b m+c n \equiv c n \quad \left(\mod m\right) \quad(b=au, c=av \text {~为整数 }).
\]
\pause
故任意整数 $a$ 与 $c n$ 同色。 
\pause
不妨设 $c$ 为正整数 (因正负同色), 此时 $c n$ 与 $c n-n$ 同色，与 $c n-2 n$ 同色，\ldots, 最终与 $n$ 同色。
\pause
既然$cn$与$n$同色，任意整数 $a$ 与 $n$ 同色。 特别知 $1,2, \cdots$, $m-1$ 共一色。

\pause
（说明：若不用同余概念， 此例的证明会很烦琐。)
\end{solution*}

\pause
\begin{comment*}%评述
  按定义 1 , “模 $m$ 同余”相当于“不计 $m$ 倍数意义下相等”, 因此“模 $m$ ”被参透称为 “抹 $m$ ”, 即抹去 $m$ 化为 0 (当然 $m$ 的倍也化为 0 ). 这一直观在运算和推理中很有用 (以后会有 “乘法的模”, 则 “模者抹去化为 1 ”). 模算术只
处理有限个“剩余”，故易。 但有时需要由剩余反推回原数的性质，称为 “提升”,就难了。 例如 Fermat 大定理的最后证明， 主要就是这提升的功夫。 论数者单道这“模算术之妙”曰：
\begin{poem}
模者抹也剩余痕，有似天女下凡尘。\\
尘世欢乐竟有限， 无翼飞升返月轮。
\end{poem}
\end{comment*}

\end{frame}


\begin{frame}{小结}
  \begin{enumerate}
    \item 何为（整数的）同余？
    \item 叙述同余的性质。多多益善。
    \item 举例说明同余的应用。
  \end{enumerate}
\end{frame}
